// https://leetcode.cn/problems/contiguous-array/

// 题干：给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

// 示例：输入: nums = [0,1]
//       输出: 2

// 碎语：相同数量的0或1，我们如果将0全部换为1，就是和为0，就转化成了和为k的最长子串长度

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int findMaxLength(vector<int>& nums)
    {
        // 本题中，哈希表的第二个int存的是下标
        // 如果出现了重复的sum,i 只保留前面的那一对
        // 默认的前缀和为0，下标为-1

        unordered_map<int, int> hash;
        hash[0] = -1;

        int sum = 0, ret = 0;
        for (int i = 0 ; i < nums.size() ; i++){
            sum += nums[i] == 0 ? -1 : 1; // 计算当前的前缀和

            if (hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {0,1};

    cout << sol.findMaxLength(nums) << endl;

    return 0;
}